// 特殊占位符的线性探查哈希表
public class ExampleLinearProbingHashMap2 {

    private static class KVNode {
        int key;
        int value;
        public KVNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 用于标记被删除元素的占位符
    // 里面的值可以随意存储，因为只会使用 == 判断指针相等，不用比较里面的值
    private final KVNode DELETED = new KVNode(-2, -2);

    // 真正存储键值对的数组
    private final KVNode[] table;

    public ExampleLinearProbingHashMap2(int capacity) {
        table = new KVNode[capacity];
    }

    // 增改
    public void put(int key, int value) {
        int index = findKeyIndex(key);
        if (index != -1) {
            // key已存在，修改对应的value
            KVNode node = table[index];
            if (node != null) {
                node.value = value;
                return;
            }
        }

        // key不存在
        KVNode node = new KVNode(key, value);
        // 在table中找到一个空位或者占位符
        index = hash(key);
        while (table[index] != null && table[index] != DELETED) {
            index = (index + 1) % table.length;
        }
        table[index] = node;
    }

    // 删除
    public void remove(int key) {
        int index = findKeyIndex(key);
        if (index == -1) {
            // key不存在，不需要remove
            return;
        }
        // 直接用占位符表示删除
        table[index] = DELETED;
    }

    // 查，返回key对应的value，如果不存在，返回-1
    public int get(int key) {
        int index = findKeyIndex(key);
        if (index == -1) {
            return -1;
        }

        return table[index].value;
    }

    // 线性探测法查找key在table中的索引
    // 如果找不到，返回-1
    private int findKeyIndex(int key) {
        // 因为删除元素是只是标记为DELETED，并不是真的删除
        // 所以table可能会被填满，导致死循环
        // step用来记录查找的步数，防止死循环
        int step = 0;
        // 注意环形数组特性
        for (int i = hash(key); table[i] != null; i = (i + 1) % table.length) {
            step++;
            // 防止死循环
            if (step > table.length) {
                return -1;
            }
            if (table[i] == DELETED)
                // 遇到占位符，直接跳过
                continue;
            if (table[i].key  == key)
                return i;
        }

        return -1;
    }

    private int hash(int key) {
        return key % table.length;
    }
}
